# 堆
"""
堆(Heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象。
    1.堆中某个节点的值总是不大于或不小于其父节点的值；
    2.堆总是一棵完全二叉树。
将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。
堆是非线性数据结构，相当于一维数组，有两个直接后继。
堆的定义如下：n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时，称之为堆。
(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4...n/2)
若将和此次序列对应的一维数组（即以一维数组作此序列的存储结构）看成是一个完全二叉树，则堆的含义表明，
完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。由此，若序列{k1,k2,…,kn}是堆，
则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）。
"""


# 算法思想
"""
不必将值一个个地插入堆中，通过交换形成堆。假设一个小根堆的左、右子树都已是堆，并且根的元素名为 ，其左右子节点为 和 ，
这种情况下，有两种可能：
    （1） 并且 ，此时堆已完成；
    （2） 或者 ，此时 应与两个子女中值较小的一个交换，结果得到一个堆，除非 仍然大于其新子女的一个或全部的两个。
    这种情况下，我们只需简单地继续这种将 “拉下来”的过程，直至到达某一个层使它小于它的子女，或者它成了叶结点。
"""
